package com.practice.sequence;

import java.util.Arrays;

/**
 * Given 3 arrays A,B,C find three indices i,j,k such that the value of 
 * I = max((a-b),(b-c),(c-a)) is minimized. (G)
 */
public class MinimizeDiff {
	/**
	 * (i, j, k) maybe not unique. For test purpose, return the minimized 
	 * maximum difference instead.
	 */
	public int minimize(int[] A, int[] B, int[] C) {
		Arrays.sort(A);
		Arrays.sort(B);
		Arrays.sort(C);
		
		int min = Integer.MAX_VALUE;
		int i = 0, j = 0, k = 0; 
		while (i<A.length && j<B.length && k<C.length) {
			int t1 = A[i] - B[j];
			int t2 = B[j] - C[k];
			int t3 = C[k] - A[i];
			
			if (t1 >= t2 && t1 >= t3) {
				if (min > t1) min = t1;
				j++;
			}
			else if (t2 >= t1 && t2 >= t3) {
				if (min > t2) min = t2;
				k++;
			}
			else {	// t3 >= t1 && t3 >= t2
				if (min > t3) min = t3;
				i++;
			}
		}
		
		return min;
	}
}
